import java.util.*;

public class Leetcode {
}

//leetcode:542:01矩阵
class Solution1 {
    //寻找方向
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    //正难则反：转为找0到这个1的最短距离
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        //创建一个数组将初值赋为-1
        int[][] dis = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                dis[i][j] =  -1;
            }
        }

        //创建队列存储坐标
        Queue<int[]> q = new LinkedList<>();

        //如果原数组中此时位置的值为0，那么我们就把dis数组这个位置的值也变为0
        for(int i = 0; i < m ; i++){
            for(int j = 0; j < n;j++){
                if(mat[i][j] == 0){
                    dis[i][j] = 0;
                    //存储0下标的位置
                    q.add(new int[]{i,j});
                }
            }
        }

        //一层一层的找0位置下标到dis数组值为-1的最短路径
        while(!q.isEmpty()){
            int[] s = q.poll();
            int a = s[0], b = s[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && dis[x][y] == -1){
                    dis[x][y] = dis[a][b]+1;
                    q.add(new int[]{x,y});
                }
            }
        }
        return dis;
    }
}

//leetcode:1020:飞地的数量
class Solution2 {
    //设置方向
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        //设置布尔数组判断这个位置是否走过
        boolean[][] visits = new boolean[m][n];

        //创建一个队列存入数组边缘位置为1的元素下标，并记录已经走过
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j< n; j++){
                if(grid[i][j] == 1){
                    if(i == 0 || i == m-1 || j == 0 || j == n-1){
                        q.add(new int[]{i,j});
                        visits[i][j] = true;
                    }
                }
            }
        }

        //一层一层的找周围元素为1的值
        while(!q.isEmpty()){
            int[] s = q.poll();
            int a = s[0], b = s[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k] , y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && !visits[x][y] && grid[x][y] == 1){
                    q.add(new int[]{x,y});
                    visits[x][y] = true;
                }
            }
        }

        //变量整个数组，得到值为1并且没有被走过的的元素个数
        int  ret = 0;
        for(int i = 0; i < m ; i++){
            for(int j = 0; j < n ; j++){
                if(grid[i][j] == 1 && !visits[i][j]){
                    ret++;
                }
            }
        }
        return ret;
    }
}